package io.github.handyang.algorithms.digraph;

import java.util.Collections;
import java.util.Stack;

/**
 * 单点有向路径
 */
@SuppressWarnings("Duplicates")
public class DFSDirectedPaths {

    private final Digraph digraph;
    //起点
    private final int s;

    private final int[] edgeTo;//起点到i路径上的最后一个点

    private final boolean[] marked;

    public DFSDirectedPaths(Digraph digraph, int s) {
        this.digraph = digraph;
        this.s = s;

        this.edgeTo = new int[digraph.V()];
        this.marked = new boolean[digraph.V()];
        dfs(s);
    }

    private void dfs(int startPoint) {
        marked[startPoint] = true;
        Iterable<Integer> adj = digraph.adj(startPoint);

        for (Integer point : adj) {
            if (marked[point]) continue;

            edgeTo[point] = startPoint;
            dfs(point);
        }
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return Collections.emptyList();

        Stack<Integer> res = new Stack<>();
        for (int w = v; w != s; w = edgeTo[w]) {
            res.push(w);
        }
        res.push(s);
        return res;
    }
}
